package com.example.algorithms.sort;

/**
 * @Author Zhang Jie
 * @Date 9/28/20
 * @Version 1.0
 */

/**
 * 计数排序
 * 一种针对特定范围之间的整数进行排序的算法。
 * 通过统计给定数组中不同元素的数量(类似于哈希映射),然后对映射后的数组进行排序输出即可
 *
 * 时间复杂度为O(n)
 * 空间复杂度与数据范围成正比，为O(n)
 * 计数排序通常用作另一个排序算法（如基数排序）的子过程
 *
 * 非原地算法，需要额外的max-min+1的（存放计数）空间和n个（存放排序后的数组）新空间
 * 稳定算法（因为count[i]+=count[i-1]这个动作）
 *
 * 优势：对于max-min+1不明显大于待排序数组的长度len,则时间复杂度比O(nlogn)的快排和归并都要优秀
 * 只能在范围不大的场景中
 *
 * 适用于负数
 * 不适用于小数的情况，也可以*10^(小数位)来将小数转变为整数
 */
public class CountingSort {

    public static int[] sort(int[] arr){
        //如果为null或者只有一个元素，则返回
        if(arr==null||arr.length<2){
            return arr;
        }

        //获取数组中的最大和最小值，已确定计数的数组大小
        int len = arr.length;
        int min=arr[0],max=arr[0];
        for(int i=0;i<len;i++){
            if(arr[i]<min){
                min=arr[i];
            }else if(arr[i]>max){
                max=arr[i];
            }
        }

        //遍历数组，获取每个值出现的次数
        //比如数组[0,1,4,1,2,5,2,4,1,8]的计数count[]为[1,3,2,0,2,1,0,0,1]
        int num=max-min+1;
        int[] count=new int[num];
        for(int i=0;i<len;i++){
            count[arr[i]-min]++;
        }
        //但是直接按计数输出不稳定，不能保证相同数字是按原顺序输出
        // 所以计数的时候，进行count[i]=count[i]+count[i-1]
        //这样结果为[1,4,6,6,8,9,9,9,10],每位与前面的差值代表了个数，而值代表了位置
        for(int i=1;i<num;i++){
            count[i]+=count[i-1];
        }

        //从后遍历数组，获取每个的位置
        int[] result = new int[len];
        for(int i=len-1;i>=0;i--){
            result[count[arr[i]-min]-1]=arr[i];
            count[arr[i]-min]--;
        }

        return result;
    }


}
